package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_15 {

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int a = 0; a < nums.length; a++) {
            if (a == 0 || nums[a] != nums[a - 1]) {
                int b = a + 1;
                int c = nums.length - 1;
                while (b < c) {
                    if (b > a + 1 && nums[b] == nums[b - 1]) {
                        b++;
                        continue;
                    }
                    int sum = nums[a] + nums[b] + nums[c];
                    if (sum == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[a]);
                        list.add(nums[b]);
                        list.add(-nums[a] - nums[b]);
                        res.add(list);
                        b++;
                        c--;
                    } else if (sum < 0) {
                        b++;
                    } else {
                        c--;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution_15 model = new Solution_15();
        System.out.println(model.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
        System.out.println(model.threeSum(new int[]{}));
        System.out.println(model.threeSum(new int[]{0}));
    }
}
